10172. Вершина

В ориентированном графе найти вершины, недостижимые из заданных вершин.

Ориентированный граф состоит из n вершин, пронумерованных последовательно 1, ..., n, и набора ребер p → q, соединяющих вершины p и q в одном направлении.

Вершина r достижима из вершины p если существует ребро p → r, или существует такая вершина q, для которой q достижима из p, а r достижима из q.

Вершина r недоступна из вершины p, если r недостижима из p.

Вход. Содержит несколько тестов. Для каждого графа первая строка содержит одно целое число n (1 ≤ n ≤ 100) – количество вершин в графе.

Далее следует группа строк, каждая из которых содержит набор целых чисел. Группа завершается строкой, содержащей одно целое число 0. Каждая строка представляет собой набор ребер. Первое целое число в наборе i является начальной вершиной, а следующая группа целых чисел j, ..., k определяет множество ребер i → j, ..., i → k, последнее целое число в строке всегда рано 0. Каждая возможная начальная вершина i (1 ≤ i ≤ n) встречается в наборе данных один раз или не встречается вообще. После каждого определения графа будет следует строка, содержащая список целых чисел. Первое целое число в строке указывает, сколько целых чисел следует за ним.

Каждое из следующих целых чисел представляет собой начальную вершину, которую необходимо исследовать. Затем идет следующий граф. Если графов больше нет, следующая строка содержит одно целое число 0.

Выход. Для каждой исследуемой начальной вершины Ваша программа должна идентифицировать все вершины, недоступные из нее. Каждый список должен отображаться в одной строке, начиная с количества недоступных вершин и заканчивая номерами недоступных вершин.

Пример входа	Пример выхода
3 1 2 0 2 2 0 3 1 2 0 0 2 1 2 0	2 1 3 2 1 3

РЕШЕНИЕ

графы – Флойд - Уоршел

Анализ алгоритма

Построим матрицу смежности графа c. Запустим алгоритм Флойда – Уоршела для поиска всех кратчайших путей в графе. Для вершины i недостижимыми будут те вершины j, для которых будет c[i][j] = ¥ после выполнения алгоритма Флойда – Уоршела. Сложность алгоритма O(n³).

Пример

Рассмотрим пример, заданный в условии.

В примере исследуются две вершины: первая и вторая. Как из первой, так и со второй вершины невозможно попасть в первую и третью вершину.

Реализация алгоритма

Входной граф храним в матрице смежности c размера MAX = 101.

#define MAX 101

int c[MAX][MAX];

Реализация алгоритма Флойда – Уоршела:

void floyd(void)

{

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if (c[i][k] + c[k][j] < c[i][j])

c[i][j] = c[i][k] + c[k][j];

}

Основная часть программы. Читаем граф и строим матрицу смежности c. Изначально полагаем все ребра равными бесконечности (в качестве бесконечности выберем шестнадцатеричное значение 3F3F3F3F). Поскольку вершины графа по условию задачи нумеруются с единицы, то нулевая строка и столбец матрицы c задействованы не будут.

while(scanf("%d",&n), n > 0)

{

memset(c,0x3F,sizeof(c));

while(scanf("%d",&a) ,a)

while(scanf("%d", &b), b) c[a][b] = 1;

Запускаем на матрице смежности c алгоритм Флойда – Уоршела.

floyd();

Читаем количество исследуемых вершин i для заданного графа, и для каждой исследуемой вершины a подсчитываем количество вершин b, недостижимых из a (для которых c[a][b] = ¥).

scanf("%d",&i);

while(i--)

{

scanf("%d",&a);

Подсчет количества вершин, недостижимых из a.

for(count = 0, b = 1; b <= n; b++)

if (c[a][b] == 0x3F3F3F3F) count++;

Выводим количество недостижимых вершин из a и сами вершины в порядке возрастания номеров.

printf("%d",count);

for(b = 1; b <= n; b++)

if (c[a][b] == 0x3F3F3F3F) printf(" %d",b);

printf("\n");

}

}

Java реализация

import java.util.*;

public class Main

{

static int c[][];

static int n;

static void floyd()

{

for(int k = 1; k <= n; k++)

for(int i = 1; i <= n; i++)

for(int j = 1; j <= n; j++)

if (c[i][k] + c[k][j] < c[i][j])

c[i][j] = c[i][k] + c[k][j];

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

while(true)

{

n = con.nextInt();

if (n == 0) break;

c = new int[n+1][n+1];

for(int i = 0; i <= n; i++)

Arrays.fill(c[i],Integer.MAX_VALUE / 2);

while(true)

{

int a = con.nextInt();

if (a == 0) break;

while(true)

{

int b = con.nextInt();

if (b == 0) break;

c[a][b] = 1;

}

}

floyd();

int i = con.nextInt();

while(i-- > 0)

{

int a = con.nextInt();

int count = 0;

for(int b = 1; b <= n; b++)

if (c[a][b] == Integer.MAX_VALUE / 2) count++;

System.out.print(count);

for(int b = 1; b <= n; b++)

if (c[a][b] == Integer.MAX_VALUE / 2) System.out.print(" " + b);

System.out.println();

}

}

con.close();

}

}